#include "heap.h"

void swap(ElemType* a, ElemType* b) {
    ElemType temp = *a;
    *a = *b;
    *b = temp;
}

int parentIndex(int child) { return (child - 1) / 2; }

/*
  在二叉堆中，无论是最大堆还是最小堆，siftUp（向上调整）操作的目的都是
  确保新插入的元素满足堆的性质。
  在最大堆中，父节点的值总是大于或等于其子节点的值；
  在最小堆中，父节点的值总是小于或等于其子节点的值。
  这意味着，对于新插入的元素，只需要确保它与其父节点满足堆的性质即可，
  不需要像siftDown（向下调整）一样比较两个兄弟节点的大小。
*/
void siftUp(ElemType* data, int child, int (*compare)(ElemType, ElemType)) {
    while (child > 0 && compare(data[child], data[parentIndex(child)]) > 0) {
        swap(&data[child], &data[parentIndex(child)]);
        child = parentIndex(child);
    }
}

/*
  在二叉堆中，无论是最大堆还是最小堆，siftDown（向下调整）操作的目的都是
  主要目的是确保在删除堆顶元素后，剩余的堆仍然满足堆的性质。
*/
void siftDown(ElemType* data, int size, int parent,
              int (*compare)(ElemType, ElemType)) {
    int left = parent * 2 + 1;
    int right = left + 1;
    int child = left;
    if (right < size && compare(data[right], data[child]) > 0) {
        child++;
    }
    if (child < size && compare(data[child], data[parent]) > 0) {
        swap(&data[child], &data[parent]);
        siftDown(data, size, child, compare);
    }
}

int defaultCompare(ElemType a, ElemType b) { return a - b; }

Heap* createHeap() {
    Heap* heap = (Heap*)malloc(sizeof(Heap));
    heap->data = (ElemType*)malloc(sizeof(ElemType) * DEFAULT_CAPACITY);
    heap->capacity = DEFAULT_CAPACITY;
    heap->size = 0;
    heap->compare = defaultCompare;
    return heap;
}

Heap* createHeapWithCompare(int (*compare)(ElemType, ElemType)) {
    Heap* heap = (Heap*)malloc(sizeof(Heap));
    heap->data = (ElemType*)malloc(sizeof(ElemType) * DEFAULT_CAPACITY);
    heap->capacity = DEFAULT_CAPACITY;
    heap->size = 0;
    heap->compare = compare;
    return heap;
}

void insert(Heap* heap, ElemType data) {
    if (heap->size == heap->capacity) {
        heap->capacity += heap->capacity >> 1;
        heap->data =
            (ElemType*)realloc(heap->data, heap->capacity * sizeof(ElemType));
    }
    heap->data[heap->size++] = data;
    siftUp(heap->data, heap->size - 1, heap->compare);
}

ElemType extract(Heap* heap) {
    ElemType ret = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    siftDown(heap->data, --heap->size, 0, heap->compare);
    return ret;
}

ElemType peek(const Heap* heap) { return heap->size == 0 ? 0 : heap->data[0]; }

size_t heapSize(const Heap* heap) { return heap->size; }

int heapEmpty(const Heap* heap) { return heap->size == 0; }

void heapSort(ElemType* data, int size) {
    for (int i = size / 2 - 1; i >= 0; --i) {
        siftDown(data, size, i, defaultCompare);
    }
    for (int i = size - 1; i > 0; i--) {
        swap(&data[0], &data[i]);
        siftDown(data, i, 0, defaultCompare);
    }
}

void heapSortWithCompare(ElemType* data, int size,
                         int (*compare)(ElemType, ElemType)) {
    for (int i = size / 2 - 1; i >= 0; --i) {
        siftDown(data, size, i, compare);
    }
    for (int i = size - 1; i > 0; i--) {
        swap(&data[0], &data[i]);
        siftDown(data, i, 0, compare);
    }
}

void deleteHeap(Heap* heap) {
    free(heap->data);
    free(heap);
}